#include<stdio.h>
#include<stdlib.h>
#define MAX_NODE 10
int UFSets[MAX_NODE];
typedef struct PTNode{
    int data;
    int parent;
}PTNode;
typedef struct PTree{
    int n;//节点个数
    PTNode nodes[MAX_NODE];
}PTree;
void Initial(int s[]){
    for(int i=0;i<MAX_NODE;i++){
        s[i]=-1;
    }
}
/*
*@返回值 返回k所属集合的根节点
*事件复杂度：worst(O(n))--和树高有关
*/
int Finder(int s[],int k){
    while(s[k]>=0)//循环找k的根
        k=s[k];
    return k;
}   
/*
*终极优化:压缩路径，先找到根节点，再将查找路径上的所有节点挂到根节点下
*h<=a(n)，增长很慢的函数
*/
int Finder_Update(int s[],int k){
    int root=k;
    while(s[root]>=0) root=s[root];
    while(k!=root){
        int t=s[k];
        s[k]=root;//k直接挂到root下
        k=t;
    }
    return root;
}
/*
*时间复杂度:合并n个独立元素--O(n^2)
*/
void union(int s[],int root1,int root2){
    //r1和r2是不同集合
    if(root1==root2)    return;
    //root2连接到root1
    s[root2]=s[root1];
} 
/*
*思路：小树往大树合并，可以防止树高增长过快
*可以用根节点的绝对值表示集合元素个数
*h<=|logn|(往下取整)+1,合并n个独立元素 worst(O(nlogn))  Finder的worst(O(nlogn))  压缩路径后O(na(n))
*/
void Union_Update(int s[],int root1,int root2){
    if(root1==root2)    return;
    if(s[root2]>s[root1]){//s[root1]树更大
        s[root1]+=s[root2];
        s[root2]=root1;
    }
    else{
        s[root2] += s[root1];
        s[root1]+=root2;
    }
}
int main(int argc,char const *argv[]){
    int s[13]={-1,0,-1,-1,1,1,2,3,3,3,4,4,7};
    return 0;
}